GATE IT 2005
Q21.
The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution? struct node {int value; struct node *next;); void rearrange (struct node *list) { struct node *p, *q; int temp; if (!list || !list -> next) return; p = list; q = list -> next; while (q) { temp = p -> value; p -> value = q -> value; q -> value = temp; p = q -> next; q = p ? p -> next : 0; } }Q22.
A dynamic RAM has a memory cycle time of 64 nsec. It has to be refreshed 100 times per msec and each refresh takes 100 nsec. What percentage of the memory cycle time is used for refreshing?Q23.
Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?Q24.
Suppose that two parties A and B wish to setup a common secret key (D-H key) between themselves using the Diffie-Hellman key exchange technique. They agree on 7 as the modulus and 3 as the primitive root. Party A chooses 2 and party B chooses 5 as their respective secrets. Their D-H key isQ25.
In a schema with attributes A, B, C, D and E following set of functional dependencies are given A \rightarrow B A \rightarrow C CD \rightarrow E B \rightarrow D E \rightarrow A Which of the following functional dependencies is NOT implied by the above set?Q26.
A table has fields F_1, F_2, F_3, F_4, F_5 with the following functional dependencies F_1 \to F_3, F_2\to F_4, (F_1 . F_2) \to F_5 In terms of Normalization, this table is inQ27.
We have two designs D1 and D2 for a synchronous pipeline processor. D1 has 5 pipeline stages with execution times of 3 nsec, 2 nsec, 4 nsec, 2 nsec and 3 nsec while the design D2 has 8 pipeline stages each with 2 nsec execution time How much time can be saved using design D2 over design D1 for executing 100 instructions?Q28.
If the trapezoidal method is used to evaluate the integral obtained \int_{0}^{1} x^2dx, then the value obtainedQ29.
Two concurrent processes P1 and P2 use four shared resources R1, R2, R3 and R4, as shown below. \begin{array}{|l|l|}\hline \textbf{P1} & \textbf{P2} \\ \text{Compute: } & \text{Compute;} \\ \text{Use $R1;$ } & \text{Use $R1;$} \\ \text{Use $R2;$ } & \text{Use $R2;$}\\ \text{Use $R3;$ } & \text{Use $R3;$} \\ \text{Use $R4;$ } & \text{Use $R4;$} \\\hline \end{array} Both processes are started at the same time, and each resource can be accessed by only one process at a time The following scheduling constraints exist between the access of resources by the processes: P2 must complete use of R1 before P1 gets access to R1. P1 must complete use of R2 before P2 gets access to R2. P2 must complete use of R3 before P1 gets access to R3. P1 must complete use of R4 before P2 gets access to R4. There are no other scheduling constraints between the processes. If only binary semaphores are used to enforce the above scheduling constraints, what is the minimum number of binary semaphores needed?Q30.
Given below is a program which when executed spawns two concurrent processes : semaphore X : = 0 ; /* Process now forks into concurrent processes P1 & P2 */ \begin{array}{|l|l|}\hline \text{$P1$} & \text{$P2$} \\\hline \text{repeat forever } & \text{repeat forever} \\ \text{$V (X) ;$ } & \text{$ P(X) ;$} \\ \text{Compute; } & \text{Compute;}\\ \text{$P(X) ;$ } & \text{$V(X) ;$} \\\hline \end{array} Consider the following statements about processes P1 and P2: I.It is possible for process P1 to starve. II.It is possible for process P2 to starve. Which of the following holds?